#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 * 归并排序 主要是合并方法吧
 *
 * */

//合并操作

void merge(int arr[], int low, int mid, int high) {
    // 合并数组 （low mid） 和 （mid+1 high）的数 存到 arr里面
    int t1l = mid - low + 1;
    int t2l = high - mid;
    int *t1 = new int[t1l];
    int *t2 = new int[t2l];

    //拷贝数组到空间
    for (int i = 0; i < mid - low + 1; ++i) {
        t1[i] = arr[low + i];
    }

    //mid+1 到 high
    for (int i = 0; i < high - mid; ++i) {
        t2[i] = arr[mid + i + 1];
    }

    //进行区间排序合并到arr

    int i = 0;
    int j = 0;

    while (i < t1l && j < t2l) {
        if (t1[i] <= t2[j]) {
            arr[low++] = t1[i++];
        } else {

            arr[low++] = t2[j++];
        }


    }

    while (i < t1l) {
        arr[low++] = t1[i++];
    }

    while (j < t2l) {
        arr[low++] = t1[j++];
    }

    delete[]t1;

    delete[]t2;
}

//分割 +合并
void Merge_sort(int a[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;//首先进行分区，然后递归操作
        Merge_sort(a, left, mid);
        Merge_sort(a, mid + 1, right);//第一次将其分为两个区间，进行合并操作

        //最后合并的时候刚好从右边 0 1 开始好像 自己没用仔细理
        merge(a, left, mid, right)
    }
    // 0 1 2 3 4 5 6
    //第一次 0 3 7
    //第二次 0 1 3
    //第三次 0 0 1
    //进行右边 0 0+1 1
    // 进行merge
    //进行右边 0 1+1 3
    // 2 2 3
    //2 2+1 3
    // 合并

}
//  Merge_sort(a,0,7);